---
title: "3、直线"
created: 2025-11-28
tags:
  - 算法
---

# 3、直线

## 题目 [直线](https://www.lanqiao.cn/paper/3829/problem/1449/)

![[image-27964247.png]]

## 思路分析

![[image-ee140f90.png]]

每两个点可以确定一条线 但线重合算同一条线

所以可以用哈希去存这些线 可以很好解决重复的问题

问题是如何存下一条线

考虑用 y=kx+b 那么只需要记录k b 即可确定一条线

那么问题就转变成了 枚举每两个点 算他们的kb 存入哈希表中

最后看哈希表的大小即可

另外 斜率不存在的情况 不好处理（斜率公式中 分子为0了）

因为是竖线 所以他和宽度有关 有多少列 就有多少条 拿出来另外处理

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef pair<double,double> PII;
set<PII> hashtable;

int main()
{
	int n,m;
	n=20,m=21;
	for(int x1=0;x1<n;x1++){
		for(int y1=0;y1<m;y1++){
			for(int x2=0;x2<n;x2++){
				for(int y2=0;y2<m;y2++){
					if(x2-x1==0)
						continue;
					if(x1==x2 && y1==y2)
						continue;
					double k=(double)(y2-y1)/(x2-x1);
//					double b=(double)y1-k*x1;//精度缺失 不能用k做乘法
					double b=(double)(x2*y1-x1*y2)/(x2-x1);
					hashtable.insert({k,b});
				}
			}
		}
	}
	cout<<hashtable.size()+n;
	return 0;
}
```

理论存在 但是因为除法会涉及精度

一开始忘了换double 用的int 对于0.5的斜率可能会被存成1

然后人傻了 用unordered\_map存 它只会把k当键 而不是k b联合键 正确应该用用PDD 加set

如果用浮点数存 也会因为精度问题表示不准确

所以斜率应该用分数表示 而不是用小数

考虑用｛｛分子，分母｝，b｝的形式当键 用gcd将分子分母化成最简形式 有点麻烦

直接用小数的话 需要用化简后的b公式 不能有缺失精度的k做乘法 ~~int b=y1-k\*x1;~~

把k的公式 带入 通分

得到 $b=(x2y1-x1y2)/(x2-x1)$

![[image-3cd6d723.png]]

所以 啧 在想出方法来之后 还有一大堆细节问题

尤其是这个精度问题 映像里已经出现三次了 除法变乘法

得把这个问题整理出来

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef pair<double,double> PII;

set<PII> hashtable;

int main()

{

	int n,m;

	n=20,m=21;

	for(int x1=0;x1<n;x1++){

		for(int y1=0;y1<m;y1++){

			for(int x2=0;x2<n;x2++){

				for(int y2=0;y2<m;y2++){

					if(x2-x1==0)

						continue;

					if(x1==x2 && y1==y2)

						continue;

					double k=(double)(y2-y1)/(x2-x1);

					double b=(double)(x2*y1-x1*y2)/(x2-x1);

					hashtable.insert({k,b});

				}

			}

		}

	}

	cout<<hashtable.size()+n;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2、卡片|2、卡片]] 🏠 [[00-刷题理模型]] ➡️ [[4、货物摆放|4、货物摆放]]